-+- Velena -+- A Connect 4 Expert System which Plays Perfectly ================================================ Abstract ======== Velena is a Shannon-C type engine written to play Connect Four. It's based on a knowledged approach that uses eight mathematical rules to take its decisions. Since the rules are proven to be correct, the conclusions made by the engine are also correct. In this way it has been possible to show that Connect Four is a first player win and Velena is always able to win when she plays first. ================================================== 1. Overview =================== 1.1. Freeware agreement ======================= This engine is to be considered freeware, which means that you can use and distribute it to anyone you want, provided no fee is charged. You should also not disassemble modify or reverse engineer the engine for any reason in any circumstance. The author's current address is: Giuliano Bertoletti Via Bocchialini n.6 Cap. 43100, Parma. Italy E-Mail: gbe32241@libero.it Fidonet: 2:332/801.6 1.2. Greetings ============== The Velena engine is based on the knowledged approach of L.Victor Allis who designed and implmented a sophisticated AI engine in a program called Victor. Velena uses the same strategy, except that even newer concepts and techinques were introduced in order to reduce the problem complexity (of solving the game) to a more tractable factor of magnitude. I also thank Filippo Ghilardi who helped me to build the opening book data base which took several days of work on his Pentium 133 computer. 2. Introduction into Connect Four ================================= Now I'll describe the rules of the game as well as some nomenclature used throughout this manual and some basic connect four strategy. 2.1. Game Rules =============== Connect Four is a two players game which takes place on a 7x6 rectangular board placed vertically between them. One player has 21 'white' men and the other 21 'black' men. Each player can drop a man at the top of the board in one of the seven columns; the man falls down and fills the lower unoccupied square. Of course a player cannot drop a man in a certain column if it's already full (i.e. it already contains six men). Even if there's no rule about which color should play first, in order to avoid confusion we will assume, as in chess, 'white' always plays first. Note however that 4Free displays men in non-white/black colors even if refered here as white and black respectively. Therefore when playing with 4Free, we call 'white' the color of the player who plays first. The object of the game is to connect four men vertically, horizontally or diagonally. If the board is filled and no one has alligned four men then the game is drawn (that is after 42 moves if no one wins). Here's an example of a game won by white (O) and black (X) in fig.1 and fig.2 respectively. A possible draw is represented in fig.3 ....... ....... oooxooo ....... ....... xxxoxxx ....... .xo.... oooxooo ...x... .xxo... xxxoxxx ...x... .oox... oooxooo xoooo.. .oxox.. xxxoxxx Fig.1 Fig.2 Fig.3 White (O) wins Black (X) wins The Game is drawn 2.2. Nomenclature ================= Since we need a way for representing a sequence of moves instead of a position, I will use the same nomenclature as the one used for chess. This means that columns are named from A to G, starting from left, and rows are numbered from 1 to 6 starting from the bottom. In this way we could represent each square of the board with a pair letter-number. For example the square in the middle of the lowest row is d1. The square above is d2 and the square on the left of d1 is c1. (see fig. 3) 6 . . . . . . . 5 . . . . . . . 4 . . . . . . . 3 . . . . . . . 2 . . . . . . . 1 . . . . . . . A B C D E F G Fig. 3 In this way we could write down a game as a sequence of moves. For example the endgame of fig.1 could have arisen from the following sequence of moves: 1) d1,d2 2) c1,d3 3) b1,a1 4) e1++ where ++ indicates the player who did that move won the game (as in chess). 2.3. Game Strategy ================== There are two kinds of strategies in connect four. The first consist in looking ahead few moves to avoid the opponent to win and in the same time trying to connect four men. The other is looking for a win in the long run. Virtually all the algorithms I have seen tend to implement the first strategy with some variants of alpha beta search and the most sophisticated ones with tree branch pruning. These strategies assure more or less the unvulnerability in the short run, but they are doomed to fail in the long run because they cannot see beyond the horizzon of few plies. Most of the games ends between 35th and 42nd move when you (or the opponent) are forced to make a particular move since there's only one column available. In this circumstance most of the people believe that the winner is lucky (if there's one). That's not it. An expert player is able to make this happen much time before. Actually this is what Velena does. The first step consist in noting that after white has moved, an odd number of free squares remains on the board. Similary after black has moved an even number of free square remains. When there's only one column available it's clear that the last square will be occupied by black (if no one wins first). Now let introduce some definitions before continuing: -------------------------------------------------- ODD SQUARE: it's a square belonging to an odd row. For example d1,c1,c3, f5 are all odd squares. EVEN SQUARE: same as above except that the row is even. For example a2, b4,c6,e2 are all even squares. GROUP: it's a set of four squares connected horizzontally, vertically or diagonally. The first player who fills a group with his men, wins. THREAT: it's a group filled with three men of the same color which has the fourth square empty, and also the square below the empty square is empty. ODD THREAT: it's a therat in a group whose empty square is odd. EVEN THREAT: same as above but the empty square is even. DOUBLE THREAT: they are two groups which share an empty odd square; each group is filled with only two men (of the same color) and the other two squares (one for each group) are empty and are one above the other. The square below the shared square must be empty too. -------------------------------------------------- It's then clear that if white has an odd threat and black cannot connect four men anywhere, the game will be eventually won by white. Please note that this is a sufficient condition and if black can connect four men somewhere, further knowledge is required. Similary if black has an even threat and white cannot connect four men the game will be eventually won by black. It's clear that in both cases we assume that players make the best move available. Things get more complex when both players have at least one group in which they can connect four men. In this case we need further investigation. If white has an odd threat and black has an even threat and the columns in which the threats are (i.e. the empty square) are different then white can still win. Of course no player must be able to connect four men except in the group in which he has the odd/even threat stated above. But if columns are the same then the lower threat (i.e. the lower empty square) wins. If both players have an odd threat the game will be drawn. Unless one of them can connect four men elsewhere. Then the strategy for white is to try to obtain an odd threat and for black an even threat. This is not always sufficient as the restrictions above shows but it's a good starting point to play connect four, especially when both players are humans. 2.4. The Way Velena Plays ========================= When set to her strongest level, Velena uses two different strategies according she's playing white or black. In both cases she uses a database for the opening lines. The database is made in such a way that Velena is always able to reach a position in which she has an odd threat when she plays white (and from there she's able to continue and win by herself). She tries to follow the longest winning line for white when she plays with black. The built in evaluation function which examines the positions is then sufficient to play the middle and end game. However, further search is done just to check for trivial wins few moves ahead. 2.5. Drawbacks of the algorithm =============================== Connect Four is not complex like chess. Therefore moves tends to repeat many times. For example the winning line for white is very narrow, so narrow that the first seven moves for white are forced. This is the reason why Velena is forced to answer almost always in the same way, given the same position on the board. There are not many variants. It's not strange that a player who keeps white men and learns how to win a game, is then always able to win each time he plays. This because he can play the same game each time. Another drawback is that Velena pays very poor attention to distinguish between a win for black and a draw. They are almost the same thing for her. Also note that Velena does the best move (when playing with white) only when she starts from the empty board. If someone sets up a position and then tells the computer to continue the game from that point, it's not warranted that the computer plays at best. Finally the algorithm tend to resign when a game is compromised and doesn't fight until the end. 3. Why Velena is so special =========================== As already said before, Velena is an expert system able to play the game perfectly. This means that if the engine is set to it's maximum level of strength she always wins when she plays first and she is almost impossible to beat when she plays second (until you make a few games and you will learn how to beat her by the engine itself). Of course if you are a beginner you can set a lower difficulty level for the computer. This is useful if you are interested in learning how to play. 3.1. Game complexity ==================== Although at first sight Connect Four doesn't seem a very complex game in terms of combinations of moves and the number of reachable different positions on the board, it should be noticed that it's not a so trivial game as it looks. Let's see some mathematics behind it. First we can make a raw estimation of game complexity noting that since each square can be empty or occupied by either white or black, each square can be in only three different states, leading a total game complexity of 3^42 which is in the order of 10^20. Of course this is an upper bound which takes in count also the illegal positions. It is possible to make some finer estimations that reduces the number of legal positions, anyway even the finest estimation gives us an order of magnitude of 7.1 x 10^13, which is still to high for a complete enumeration. To build up a brute force attack several terabytes of disk space would be required, and current technology is far away from this possibility. Besides the space requirements, also the time requirements would be out of what are called "reasonable resources". Finally it would be almost impossible to distribute the engine. 3.2. So Velena is not a brute force attack? ================================================== Definitly not. Velena is an intelligent engine which is able to predict the final result of a game using complex mathematics, and efficient search strategies. The engine is compact and strong; only a tiny opening book of about 60.000 positions is used for the opening lines. All the rest is calculated on fly. 3.3. Why should I use Velena if it's unbeatible? ================================================== Well, there are several reasons why this engine can be useful. First it represents the final word on Connect 4 (or so I hope): no program or living man can outperform Velena. Besides, Velena is very useful to train yourself against a human player. If you want to become a strong player then you should train yourself with a strong player. And Velena is the strongest. 3.4. But is Velena really so perfect? ===================================== Well, it's perfect in the sense that she's always able to win if she plays first. This because it can be mathematically shown that Connect Four can be won by the player which plays first (if it plays well) no matter how good the opponent is. Of course if Velena plays second, there's still a chance for the human player to defeat her. Once you learned how, you can easiliy win. More over the purpose of the computer in this case (when playing second) is not to win, but to avoid losing, if possible. In other words Velena considers a draw a good result if it plays with red men. 3.5. So Velena destroyed Connect Four? ====================================== Yes, but humans are humans and machines are machines. Connect Four is still interesting if played between two men. Of course there are no chances between a man and a computer, like there are no chances between a man and a car. The latter will run always faster. 3.6. Why does Velena play almost always the same game when she's in autoplay? ================================================== Connect four is not like chess. Even if the game is not as trivial as tic tac toe, the complexity is much smaller than chess. This of course leads to a limited number of variants and often the moves are forced. For example there's only one winning way for white and the first seven moves are forced for him. If he choses another move, black can draw. Similary black has only one strong defensive line (which of course fails in the long run) which can protect him from a premature loss. It's clear that once you learn how to infiltrate in this line, you are likely to win each time against black. 3.7. Where can I find the complete description of the algorithms used here? ================================================== You can try: ftp://ftp.cs.vu.nl/~victor/connect4.zip ftp://ftp.cs.vu.nl/~victor/thesis.zip this is the documentation made available by L.Victor Allis and surely it's very interesting. Of course I am not sure that it will be there forever. Please contact victor@cs.vu.nl for more information. Keep also in mind that this engine is based on his theory but it does not follow it completely. For example the mathematical rules have been reduced from nine to eight. You can also refer to Velena Home Page at: http://www.ce.unipr.it/~gbe/velena.html 3.8. Where can I get the last version of the Original Velena program? =============================================== Check out Velena's Home Page at: http://www.ce.unipr.it/~gbe/velena.html or use a net serach engine. 3.9. Is the source code of Velena available to the public? ================================================== No, at the moment it's not. Maybe one day it will. 3.10. Who's F.Alinovi and why did he say: "...who wants to make four?" ================================================== He's a friend. After I bored him telling the inner workings of Velena and the clever idea behind the algorithm he answered that way. He also added that I was losing my time. Poor little fellow! :)))) 3.11. What's "a Shannon-C type program" mean? ============================================= In his famous paper in 1950 C.Shannon describes three methods by which a machine could play a strategy game (such chess, checkers, connect four and so on...). The C-type method consist in emulating human mind to take decisions. In other words the eight mathematical rules Velena uses are not based on a search algorithm but on the properties of the game. The A-type method instead is based on pure brute force search. Just to be fair Velena is not only a Shannon-C type engine since it also uses some search algoritms to play, anyway the great difference in playing capabilities relies just on this knowledged approach, which made possible to solve the game. 3.12 Why isn't there the possibility to change the board size? ================================================== I think the standard 7x6 board is enough. Other sizes are not very interesting. For example it can easily be shown that black can draw on any (2n)x6 board. Here's the 6x6 board algorithm black can use to draw any game. step 1: if white plays column A,B,E or F, you play follow up (the same column). step 2: when white plays column C or D for the first time you answer in the other column. step 3: if white plays column C or D again you answer in the same column until the column is full. If you cannot answer that way because the column is full, then you play the other column. If black follows these three steps, the game can be drawn, no matter what white does. 3.13 Why did you call her Velena? ================================= I don't know, I simply liked the name. However it's very similar to "Veleno" which in italian means "poison". The intro logo from the original game recalls this sensation too. I have nothing else to say about it. :-((( ====================================================== Further details will be given if requested. Please write in english or in italian. ====================================================== The author: Giuliano Bertoletti Via Bocchialini n.6 Cap. 43100 Parma gbe32241@libero.it